package com.cat.greedyAlgorithm;

import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-average-pass-ratio/description/?envType=daily-question&envId=2025-09-01
 * @create 2025/9/1 11:01
 * @since JDK17
 */

public class Solution40 {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<int[]> heap = new PriorityQueue<>(((o1, o2) -> {
            long a = o1[1] - o1[0], b = o2[1] - o2[0];
            long val1 = a * (o2[1] + 1) * o2[1];
            long val2 = b * (o1[1] + 1) * o1[1];
            return Long.compare(val2, val1);
        }));  //
        // 加入堆中
        for (int[] cls : classes) {
            heap.add(cls);
        }
        for (int i = 0; i < extraStudents; i++) {
            int[] poll = heap.poll();
            heap.add(new int[]{poll[0] + 1, poll[1] + 1});
        }
        double ans = 0;
        while (!heap.isEmpty()) {
            int[] poll = heap.poll();
            ans += ((double) poll[0]) / poll[1];
        }
        return ans / classes.length;
    }
}
